package javatest.test;

 
class Solution {
    public int longestIncreasingPath(int[][] matrix) {
        int result = 0;
        int rows = matrix.length;
        int cols = matrix[0].length;
        int[][] dp = new int[rows][cols];
        
        for (int i=0; i<rows; i++){
            for(int j=0; j<cols; j++) {
                if (dp[i][j] == 0){
                    dp[i][j] = longest(matrix, i, j, dp);
                }
                result = Math.max(result, dp[i][j]);
            }
        }

        return result;
    }
    private int longest(int[][] matrix, int i, int j, int[][] dp) {
        if (dp[i][j] != 0) {
            return dp[i][j];
        }
        int longestFromCurrent = 1;
        int current = matrix[i][j];
        if (i > 0 && matrix[i-1][j] > current) {
            longestFromCurrent = Math.max(longestFromCurrent, dp[i-1][j]+1);
        }
        if (i < matrix.length -1 && matrix[i+1][j] > current) {
            longestFromCurrent = Math.max(longestFromCurrent, dp[i+1][j]+1);
        }
        if (j > 0 && matrix[i][j-1] > current) {
            longestFromCurrent = Math.max(longestFromCurrent, dp[i][j-1]+1);
        }
        if (j < matrix[0].length -1 && matrix[i][j+1] > current) {
            longestFromCurrent = Math.max(longestFromCurrent, dp[i][j+1]+1);
        }
        return longestFromCurrent;
    }

public static void main(String[] args) {
    Solution s = new Solution();
    s.maxSubArray(new int[]{-2,1,-3,4,-1,2,1,-5,4,9,0,-1,-10,20});
    // s.maxSubArray(new int[]{15, -1,-10,20});
}
}
